package MiddlePractice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Demo1631 {
	
//	1631. 最小体力消耗路径
//	你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。
//	一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
//	你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
//
//	一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
//
//	请你返回从左上角走到右下角的最小 体力消耗值 。
	
	public int minimumEffortPath(int[][] heights) {
		int[][] minEnergeTo = new int[heights.length][heights[0].length];
		for(int i=0; i<minEnergeTo.length; i++) {
			Arrays.fill(minEnergeTo[i], Integer.MAX_VALUE);
		}
		minEnergeTo[0][0] = 0;
		
		PriorityQueue<State> pq = new PriorityQueue<>((a, b)->(a.minEnergeFromStart-b.minEnergeFromStart));
		pq.offer(new State(new int[] {0, 0}, 0));
		
		while(!pq.isEmpty()) {
			State curState = pq.poll();
			int locationX = curState.vexId[0];
			int locationY = curState.vexId[1];
			int energeFormStart = curState.minEnergeFromStart;
			
			if(locationX == heights.length-1 && locationY == heights[0].length - 1) {
				return energeFormStart;
			}
			
			if(energeFormStart > minEnergeTo[locationX][locationY])
				continue;
			
			for(int[] neighbor : getAdjLocation(locationX, locationY, heights)) {
				int nextX = neighbor[0];
				int nextY = neighbor[1];
				int energeToNext = Math.max(Math.abs(heights[locationX][locationY]-heights[nextX][nextY])
										, minEnergeTo[locationX][locationY]);
				
				if(energeToNext < minEnergeTo[nextX][nextY]) {
					minEnergeTo[nextX][nextY] = energeToNext;
					pq.offer(new State(new int[] {nextX, nextY}, energeToNext));
				}
			}
		}
		
		return -1;
    }


	private List<int[]> getAdjLocation(int locationX, int locationY, int[][] heights) {
		int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
		List<int[]> neighbors= new LinkedList<>();
		for(int[] nextLoc : dirs) {
			int nextLocX = locationX + nextLoc[0];
			int nextLocY = locationY + nextLoc[1];
			if(nextLocX < 0 || nextLocX >= heights.length || nextLocY < 0 || nextLocY >= heights[0].length) {
				continue;
			}
			neighbors.add(new int[] {nextLocX, nextLocY});
		}
		
		return neighbors;
	}


	private class State {
		public int[] vexId;
		public int minEnergeFromStart;
		public State(int[] vexId, int minEnergeFromStart) {
			this.vexId = vexId;
			this.minEnergeFromStart = minEnergeFromStart;
		}
	}
	
	
}
